package com.leetcode.algorithm.y19.m04;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)349. 两个数组的交集
 * (done)202. 快乐数
 * (done)350. 两个数组的交集 II
 * (done)242. 有效的字母异位词
 * (done)205. 同构字符串
 * (done)451. 根据字符出现频率排序
 * @author: jie.deng
 * @time: 2019年4月21日 下午7:52:26
 */
public class MySolution0421 {
    
    /**
     * 349. 两个数组的交集 
     * 给定两个数组，写一个函数来计算它们的交集。
     * 
     * 例子:
     * 给定 num1= [1, 2, 2, 1], nums2 = [2, 2], 
     * 返回 [2].
     * 
     * 提示:
     * 每个在结果中的元素必定是唯一的。 
     * 我们可以不考虑输出结果的顺序。
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        for (int num : nums1) {
            set1.add(num);
        }
        int idx = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (set1.contains(nums2[i])) {
                nums2[idx++] = nums2[i];
                set1.remove(nums2[i]);  // 每个在结果中的元素必定是唯一的
            }
        }
        return Arrays.copyOfRange(nums2, 0, idx);
    }
    
    /**
     * 202. 快乐数
     * 
     * 编写一个算法来判断一个数是不是“快乐数”。
     * 
     * 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
     * 
     * 示例: 
     * 
     * 输入: 19
     * 输出: true
     * 解释: 
     * 12 + 92 = 82
     * 82 + 22 = 68
     * 62 + 82 = 100
     * 12 + 02 + 02 = 1
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        return isHappy(n, new HashSet<Integer>());
    }
    
    private boolean isHappy(int num, Set<Integer> set) {
        if (num == 1) {
            return true;
        }
        if (set.contains(num)) {
            return false;
        }
        set.add(num);
        int sum = 0;
        while (num > 0) {
            sum += (num % 10) * (num % 10);
            num = num / 10;
        }
        return isHappy(sum, set);
    }

    /**
     * 350. 两个数组的交集 II 
     * 给定两个数组，写一个方法来计算它们的交集。
     * 
     * 例如: 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 
     * 返回 [2, 2].
     * 
     * 注意：
     * 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。 
     * 我们可以不考虑输出结果的顺序。 
     * 
     * 跟进:
     * 如果给定的数组已经排好序呢？你将如何优化你的算法？ 
     * 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
     * 如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        // key为num1中的元素，value为出现的次数
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            map1.put(num, map1.get(num) == null ? 1 : 1 + map1.get(num));
        }

        int idx = 0;
        for (int i = 0; i < nums2.length; i++) {
            Integer cnt = map1.get(nums2[i]);
            if (cnt != null) {
                // 交集
                nums2[idx++] = nums2[i];
                if (cnt == 1) {
                    map1.remove(nums2[i]);
                } else {
                    map1.put(nums2[i], cnt - 1);
                }
            }
        }
        return Arrays.copyOfRange(nums2, 0, idx);
    }
    
    /**
     * 242. 有效的字母异位词 
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
     * 
     * 示例 1:
     * 输入: s = "anagram", t = "nagaram" 
     * 输出: true 
     * 
     * 示例 2:
     * 输入: s = "rat", t = "car" 
     * 输出: false 
     * 
     * 说明: 你可以假设字符串只包含小写字母。
     * 
     * 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
     * 
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s == null || t == null) {
            return s == t;
        }
        if (s.length() != t.length()) {
            return false;
        }
        if (s.equals(t)) {
            return true;
        }
        Map<Character, Integer> sMap = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            sMap.put(ch, sMap.get(ch) == null ? 1 : 1 + sMap.get(ch));
        }
        Map<Character, Integer> tMap = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            Character ch = t.charAt(i);
            tMap.put(ch, tMap.get(ch) == null ? 1 : 1 + tMap.get(ch));
        }
        if (sMap.size() != tMap.size()) {
            return false;
        }
        for (Character ch : sMap.keySet()) {
            if (!Objects.equals(sMap.get(ch), tMap.get(ch))) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 205. 同构字符串 
     * 给定两个字符串 s 和 t，判断它们是否是同构的。
     * 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
     * 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
     * 
     * 示例 1:
     * 输入: s = "egg", t = "add" 
     * 输出: true 
     * 
     * 示例 2:
     * 输入: s = "foo", t = "bar" 
     * 输出: false 
     * 
     * 示例 3:
     * 输入: s = "paper", t = "title" 
     * 输出: true 
     * 
     * 说明: 你可以假设 s 和 t 具有相同的长度。
     * 
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        // 说明: 你可以假设 s 和 t 具有相同的长度。
        int len = s.length();
        Map<Character, Character> map = new HashMap<Character, Character>();
        for (int i = 0; i < len; i++) {
            Character ch = s.charAt(i);
            if (map.containsKey(ch)) {
                if (map.get(ch).charValue() != t.charAt(i)) {
                    return false; // 如果相同的key映射到不同的value，不是同构字符串
                }
            } else {
                Character tCh = t.charAt(i);
                if (map.values().contains(tCh)) {
                    return false; // 如果不同的key映射到相同的value，不是同构字符串
                }
                map.put(ch, t.charAt(i));
            }
        }
        return true;
    }
    
    /**
     * 451. 根据字符出现频率排序
     * 
     * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
     * 
     * 示例 1:
     * 
     * 输入:
     * "tree"
     * 
     * 输出:
     * "eert"
     * 
     * 解释:
     * 'e'出现两次，'r'和't'都只出现一次。
     * 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
     * 示例 2:
     * 
     * 输入:
     * "cccaaa"
     * 
     * 输出:
     * "cccaaa"
     * 
     * 解释:
     * 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
     * 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
     * 示例 3:
     * 
     * 输入:
     * "Aabb"
     * 
     * 输出:
     * "bbAa"
     * 
     * 解释:
     * 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
     * 注意'A'和'a'被认为是两种不同的字符。
     * @param s
     * @return
     */
    public String frequencySort(String s) {
        if (s == null || s.length() <= 2) {
            return s;
        }
        int len = s.length();
        Map<Character, Integer> cntMap = new HashMap<Character, Integer>(); // key为字符串里的字符，value为出现的频率
        for (int i = 0; i < len; i++) {
            Character ch = s.charAt(i);
            cntMap.put(ch, cntMap.get(ch) == null ? 1 : 1 + cntMap.get(ch));
        }
        // cntMap的value的范围[0,len], 将出现频率直接映射数组索引，可以实现按照出现的频率降序排列
        StringBuilder[] strArr = new StringBuilder[len + 1];
        for (Map.Entry<Character, Integer> entry : cntMap.entrySet()) {
            char ch = entry.getKey().charValue();
            int cnt = entry.getValue().intValue();
            char[] chs = new char[cnt];
            Arrays.fill(chs, ch);
            if (strArr[cnt] == null) {
                strArr[cnt] = new StringBuilder();
            }
            strArr[cnt].append(chs);
        }
        StringBuilder retBuilder = new StringBuilder();
        for (int i = len; i >= 1; i--) { // 按照出现的频率降序排列
            if (strArr[i] != null) {
                retBuilder.append(strArr[i]);
            }
        }
        return retBuilder.toString();
    }
    
}
